package personal.leil.learning.disjoint;

/**
 * Created by Leil on 21.1.24
 */
public class DisjointSet {
    private int[] parent;

    public DisjointSet(int size) {
        parent = new int[size];
        // 初始化时，每个元素的父节点是自身
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    // Find 操作
    public int find(int element) {
        if (parent[element] != element) {
            parent[element] = find(parent[element]); // 路径压缩
        }
        return parent[element];
    }

    // Union 操作
    public void union(int set1, int set2) {
        int root1 = find(set1);
        int root2 = find(set2);
        parent[root1] = root2; // 或者 parent[root2] = root1;
    }
}
